from LibJeuDeRockse import *

# Grille de jeu du sujet
T = [[2, -4, -6, 0],
    [1, -2, 2, 3],
    [-2, 2, -3, 4],
    [-1, 4, -3, 7]]

sauts = [(0, 1), (1, -1), (1, 1)]   # Sauts par défaut
bonus = {(1, 2): [(1, 0)]}          # Case bonus en (1,2)

chemin_optimal = [(0, 0), (0, 1), (0, 2), (1, 1), (1, 2), (2, 2), (3, 2), (3, 3)]

####################################
# Partie 1 : Sauts et chemins
####################################
print("\nPARTIE 1")
print("----------")

# Question 1
print("poids du chemin optimal:")
print(poids(T, chemin_optimal))

# Question 2
# La complexité est de O(L) où L est la longueur du chemin (nombre de cases).
# On parcourt chaque case une fois et l'accès à T[i][j] est en O(1).

# Question 3
liste_sauts = []
print("\nCase atteinte après les 4 premiers déplacements du chemin optimal")
liste_sauts = [sauts[0], sauts[0], sauts[0], sauts[1]]
print(appliquer_sauts(0, 0, liste_sauts))

# Question 4
print("\nLes sauts par défaut, associés au bonus en case (1,2) sont en accord avec le chemin optimal :")
print(sauts_corrects(sauts,bonus,chemin_optimal))
print("\nPar contre sans le bonus, ces sauts par défaut ne sont pas en accord avec le chemin optimal car le saut (1,0) est interdit :")
print(sauts_corrects(sauts,{},chemin_optimal))


# Question 5
print("Les sauts par défaut sont bien formés avec ou sans le bonus le bonus")
print(sauts_bien_formes(sauts,{}))
print(sauts_bien_formes(sauts,bonus))
print("Mais avec le bonus (0,-1) (déplacement à gauche) ils ne sont plus bien_formés")
print(sauts_bien_formes(sauts,{(1,2):[(0,-1)]}))

########################################
# Partie 2 : Recherche exhaustive
########################################
print("\nPARTIE 2")
print("----------")
print("Avec sauts_max=100, le chemin optimal est trouvé par recherche exhaustive avec un poids de -7")
print("Ce chemin passe par la case bonus (1,2) et utilise le saut (1,0) débloqué :")
print(trouve_complet(T,sauts,bonus,100))

print("\nAvec sauts_max = 5, on ne trouve pas un chemin jusqu'à l'arrivée")
print(trouve_complet(T,sauts,bonus,5))

print("\nSans bonus et avec sauts_max=100, on trouve le chemin optimal avec un poids de -6:")
print("Cela montre l'importance des cases bonus")
print(trouve_complet(T,sauts,{},100))

print("\nAppel avec mémoïsation")
print(trouve_complet_memo(T,sauts,{},100,{}))

########################################
# Partie 3 : Recherche gloutonne
########################################
print("\nPARTIE 3")
print("----------")
print("\nRecherche récursive depuis (0,0) avec k=2 : (0,0) -> (0,2)")
print(trouve_complet(T,sauts,bonus,2,0,0))
print("Recherche récursive depuis (0,2) avec k=2 : (0,2) -> (2,2)")
print(trouve_complet(T,sauts,bonus,2,0,2))
print("Recherche récursive depuis (2,2) avec k=2 : (2,2) -> (3,2)")
print(trouve_complet(T,sauts,bonus,2,2,2))
print("Recherche récursive depuis (3,2) avec k=2 : (3,2) -> (3,3)")
print(trouve_complet(T,sauts,bonus,2,3,2))
print("On trouve le chemin : [(0,0),(0,1),(0,2),(1,1),(2,2),(2,3),(3,2),(3,3)]")
print("poids du chemin : non optimal")
print(poids(T,[(0,0),(0,1),(0,2),(1,1),(2,2),(2,3),(3,2),(3,3)]))


print("\nRecherche récursive depuis (0,0) avec k=3 : (0,0) -> (1,1)")
print(trouve_complet(T,sauts,bonus,3,0,0))
print("Recherche récursive depuis (1,1) avec k=3 : (1,1) -> (3,2)")
print(trouve_complet(T,sauts,bonus,3,1,1))
print("Recherche récursive depuis (3,2) avec k=3 : (3,2) -> (3,3)")
print(trouve_complet(T,sauts,bonus,3,3,2))
print("On trouve le chemin : [(0,0),(0,1),(0,2),(1,1),(1,2),(2,2),(3,2),(3,3)]")
print("poids du chemin : non optimal")
print(poids(T,[(0,0),(0,1),(0,2),(1,1),(1,2),(2,2),(3,2),(3,3)]))

def trouve_glouton(T,sauts,bonus,k):
    case_finale = (len(T)-1,len(T)-1)
    case = (0,0)
    chemin = [(0,0)]         # Pour enregistrer le chemin

    while case != case_finale:
        # Cherche les meilleures actions à l'horizon k
        _, actions = trouve_complet(T,sauts,bonus,k,case[0],case[1])

        # Applique les actions et enregistre les poids
        for a in actions:
            # position initiale
            i = case[0]
            j = case[1]

            # Applique l'action sur la case courante
            case = appliquer_sauts(i,j,[a])

            # Sauvegarde le chemin
            chemin.append(case)
    return chemin, poids(T,chemin)

print("\nRecherche gloutonne depuis (0,0) avec k=2:")
print(trouve_glouton(T,sauts,bonus,2))
print("\nRecherche gloutonne depuis (0,0) avec k=3:")
print(trouve_glouton(T,sauts,bonus,3))
print("\nRecherche gloutonne depuis (0,0) avec k=4:")
print(trouve_glouton(T,sauts,bonus,4))


########################################
# Partie 4 : Programmation dynamique
########################################
def code_bonus(masque_bonus):
    code = 0
    for i in range(len(masque_bonus)):
        code = code + masque_bonus[i]*2**i
    return code

def combinaisons_bonus(nb_bonus):
    file=[[True for i in range(nb_bonus)]]
    masques = [file[0]]

    # On défile tant que la file n'est pas vide
    while len(file) !=0:
        choix = file.pop(0)

        # Insère une coordonnée True -> False
        for i,val in enumerate(choix):
            modif = choix[:]
            if val == True:
                modif[i] = False
                if modif not in file:
                    file.append(modif)
                    masques.append(modif)
    return masques

def trouver_sauts_possibles(sauts,bonus_au_rang,masque_bonus):
    # Exemples de paramètres:
    # sauts = [(0, 1), (1, -1), (1, 1)]
    # bonus_au_rang = [[(1, 0), (0, 1)], [(-1, -1)], [(-1,1)]]
    # masque_bonus = [False, True, False]

    # Les sauts par défaut sont des sauts possibles
    sauts_possibles = sauts[:]

    # Pour chaque k=True, récupère les sauts associés
    # et les ajoute aux sauts possibles
    for k in range(len(masque_bonus)):
        if masque_bonus[k] == True:
            # ajoute les sauts associés au rang k
            for saut in bonus_au_rang[k]:
                sauts_possibles.append(saut)
    return sauts_possibles


def trouve_dynamique(T,sauts,bonus):
    N = len(T)
    nb_bonus = len(bonus)
    nb_code_bonus = 2**nb_bonus

    # Format poids_opt : (i,j,nb_code_bonus)
    poids_opt = [[[INFINI for bonus_code in range(nb_code_bonus)]
                          for j in range(N)]
                          for i in range(N)]

    # Format saut_opt : (i,j,nb_code_bonus)
    saut_opt = [[[(0,0,0) for bonus_code in range(nb_code_bonus)]
                          for j in range(N)]
                          for i in range(N)]

    # Récupère les bonus et les rangs associés
    (bonus_au_rang ,rang_du_bonus) = ranger_bonus(bonus)

    # Itère sur toutes les combinaisons des masques bonus possibles
    # par ordre décroissant au sens de l'inclusion
    for bonus_actifs in combinaisons_bonus(nb_bonus):
        # Récupère le code_bonus associé au masque courant
        code_bonus_actifs = code_bonus(bonus_actifs)

        # Cas de base sur la case (N-1, N-1)
        poids_opt[N-1][N-1][code_bonus_actifs] = T[N-1][N-1]

        # Récupère les sauts possibles depuis la case finale
        # pour les différentes possibilités des masques bonus
        sauts_possibles = trouver_sauts_possibles(sauts,bonus_au_rang,bonus_actifs)

        # Itération à l'envers sur les (i,j) en partant de (N-1)->0
        for i in range(N-1,-1,-1):
            for j in range(N-1,-1,-1):
                if i == N-1 and j == N-1:
                    continue

                # Mise à jour des bonus disponibles sur la case (i,j)
                # pour le masque bonus_actif courant
                code_bonus_dest = ajouter_bonus(bonus,rang_du_bonus,i,j,bonus_actifs,code_bonus_actifs)

                # Si la case (i,j) est dans les bonus alors ajoute le bonus aux sauts possibles
                # depuis cette case
                if (i,j) in bonus:
                    sauts_possibles_final = sauts_possibles + bonus[(i,j)]
                else:
                    sauts_possibles_final = sauts_possibles

                # Recherche du poids_opt[i_s][j_s][code_bonus] minimum
                # parmi tous les successeurs
                for (delta_i ,delta_j) in sauts_possibles_final:
                    # Calcul de la case du successeur
                    i_dest = i + delta_i
                    j_dest = j + delta_j

                    # Si le successeur est bien dans la grille
                    if (i_dest in range(N) and j_dest in range(N)):
                        # Applique la récurrence
                        poids_opt_dest = poids_opt[i_dest][j_dest][code_bonus_dest]

                        # Compare le poids et enregistre le poids minimum
                        # dans poids_opt[i][j][code_bonus]
                        if (poids_opt[i][j][code_bonus_actifs] > poids_opt_dest):
                            poids_opt[i][j][code_bonus_actifs] = poids_opt_dest
                            saut_opt[i][j][code_bonus_actifs] = (delta_i,delta_j,code_bonus_dest)

                # Ajoute T[i][j] au poids du successeur optimum trouvé
                poids_opt[i][j][code_bonus_actifs] += T[i][j]

    return (poids_opt, saut_opt)

def solution_dynamique(saut_opt,N):
    # case de départ
    case = (0,0)
    code_bonus = 0

    # Sauvegarde du chemin
    chemin = [case]

    # Tant qu'on n'est pas arrivé sur la case finale
    while case[0] != N-1 or case[1] != N-1:
        # Récupère le saut optimum
        saut = saut_opt[case[0]][case[1]][code_bonus]

        if (saut[0], saut[1], saut[2]) == (0, 0, 0):
            return []  # pas de chemin


        # Applique le saut et le code
        case = (case[0] + saut[0], case[1] + saut[1])

        # Met à jour le code_bonus
        code_bonus = saut[2]

        # Met à jour le chemin
        chemin.append(case)

    return chemin


print("\nPARTIE 4")
print("----------")
print("\nFonction code_bonus pour [True,False] :")
print(code_bonus([True,False]))

print("\nCombinaisons des masques pour nb_bonus = 3 :")
print(combinaisons_bonus(3))

print("\nTest de la fonction ranger_bonus() avec le bonus par défaut: {(1, 2): [(1, 0)]}")
bonus_au_rang, rang_du_bonus = ranger_bonus(bonus)
print("bonus_rang=" + str(bonus_au_rang))
print("rang_du_bonus=" + str(rang_du_bonus))

print("\nTest de la fonction ranger_bonus() avec le bonus {(1, 2): [(1, 0),(-1,0)], (1,3):[(-1,-1)]}")
bonus_au_rang, rang_du_bonus = ranger_bonus({(1, 2): [(1, 0),(-1,0)], (1,3):[(-1,-1)]})
print("bonus_au_rang=" + str(bonus_au_rang))
print("rang_du_bonus=" + str(rang_du_bonus))

print("\nTest de la fonction trouver_sauts_possibles:")
sauts = [(0, 1), (1, -1), (1, 1)]
bonus = {(1, 2): [(1, 0),(-1,0)], (1,3):[(-1,-1)]}
bonus_au_rang, rang_du_bonus = ranger_bonus(bonus)
print("Retourne les sauts par défaut:")
print(trouver_sauts_possibles(sauts, bonus_au_rang, [False,False]))
print("Retourne les sauts par défaut + les sauts de rang 1:")
print(trouver_sauts_possibles(sauts, bonus_au_rang, [False,True]))
print("Retourne les sauts par défaut + les sauts de rang 0:")
print(trouver_sauts_possibles(sauts, bonus_au_rang, [True,False]))
print("Retourne les sauts par défaut + les sauts de rang 0 et 1:")
print(trouver_sauts_possibles(sauts, bonus_au_rang, [True,True]))

print("\nTest de la fonction ajouter_bonus:")
bonus = {(1, 2): [(1, 0)], (2, 1): [(0, 1)]}
masque = [False,False]
print("bonus:",bonus)
print("masque:",masque,"(code_bonus=",code_bonus(masque),")")
bonus_au_rang, rang_du_bonus = ranger_bonus(bonus)
print("Ajoute le bonus de la case (1,2) :")
print("code_bonus retourné :", ajouter_bonus(bonus, rang_du_bonus, 1, 2, masque, code_bonus(masque)))

masque = [False,False]
print("bonus:",bonus)
print("masque:",masque,"(code_bonus=",code_bonus(masque),")")
bonus_au_rang, rang_du_bonus = ranger_bonus(bonus)
print("Ajoute le bonus de la case (2,1) :")
print("code_bonus retourné :", ajouter_bonus(bonus, rang_du_bonus, 2, 1, masque, code_bonus(masque)))

masque = [True,False]
print("bonus:",bonus)
print("masque:",masque,"(code_bonus=",code_bonus(masque),")")
bonus_au_rang, rang_du_bonus = ranger_bonus(bonus)
print("Ajoute le bonus de la case (2,1) :")
print("code_bonus retourné :", ajouter_bonus(bonus, rang_du_bonus, 2, 1, masque, code_bonus(masque)))

print("\nTest de la fonction trouve_dynamique")
# Grille de jeu du sujet
T = [[2, -4, -6, 0],
    [1, -2, 2, 3],
    [-2, 2, -3, 4],
    [-1, 4, -3, 7]]

sauts = [(0, 1), (1, -1), (1, 1)]   # Sauts par défaut
bonus = {(1, 2): [(1, 0)]}          # Case bonus en (1,2)
poids_opt, saut_opt = trouve_dynamique(T,sauts,bonus)
poids_opt2, saut_opt2 = trouve_dynamique(T,sauts,{})

print("Poids optimal depuis la case [0][0] avec bonus en case (1,2):", poids_opt[0][0][0])
print("Poids optimal depuis la case [0][0] sans bonus en case (1,2):", poids_opt2[0][0][0])
print("Sauts optimaux depuis la case [1][1] avec bonus en case (1,2):", saut_opt[1][1])
print("Sauts optimaux depuis la case [1][2] avec bonus en case (1,2):", saut_opt[1][2])

print("\nCalcul du chemin optimal", solution_dynamique(saut_opt,len(T)))

# Chemin impossible
T = [[0, 0, 0, 0],
     [0, 0, 0, 0],
     [0, 0, 0, 0],
     [0, 0, 0, 0]]

sauts = [(1, 0)]          # on descend uniquement
bonus = {}                # pas de bonus

poids_opt, saut_opt = trouve_dynamique(T,sauts,bonus)
print("\nCalcul du chemin optimal", solution_dynamique(saut_opt,len(T)))